package com.fh.binarysearch;

/**
 * T34.在排序数组中查找元素的第一个和最后一个位置
 * @date: 2025/10/14 21:45
 */
public class T34SearchRange {
    class Solution {
        public int[] searchRange(int[] nums, int target) {
            // 处理空数组或目标值不可能存在的快速返回
            if (nums.length == 0 || nums[0] > target || nums[nums.length - 1] < target) {
                return new int[]{-1, -1};
            }

            int leftBorder = findLeftBorder(nums, target);
            // 如果左边界没找到，说明目标值不存在，直接返回[-1, -1]
            if (leftBorder == -1) {
                return new int[]{-1, -1};
            }
            int rightBorder = findRightBorder(nums, target);
            return new int[]{leftBorder, rightBorder};
        }

        private int findLeftBorder(int[] nums, int target) {
            int left = 0;
            int right = nums.length - 1;
            while (left < right) {
                int mid = left + (right - left) / 2; // 默认向下取整
                if (nums[mid] < target) {
                    // 目标值在右侧，缩小左边界
                    left = mid + 1;
                } else { // nums[mid] >= target
                    // 目标值在mid或其左侧，缩小右边界（注意这里包括等于的情况）
                    right = mid;
                }
            }
            // 循环结束，left==right，检查是否找到目标
            return nums[left] == target ? left : -1;
        }

        private int findRightBorder(int[] nums, int target) {
            int left = 0;
            int right = nums.length - 1;
            while (left < right) {
                // 注意：这里加1，是向上取整，避免死循环的关键
                int mid = left + (right - left + 1) / 2;
                if (nums[mid] > target) {
                    // 目标值在左侧，缩小右边界
                    right = mid - 1;
                } else { // nums[mid] <= target
                    // 目标值在mid或其右侧，缩小左边界（注意这里包括等于的情况）
                    left = mid;
                }
            }
            // 由于先找了左边界且已做检查，这里left指向的必然是目标值
            return left;
        }
    }
}
